import java.util.HashMap;
import java.util.Map;
public class Solution {
    public static int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer, Integer> map = new HashMap<>();
        int value;
        for(int i=0; i<array.length; i++){
            if(map.containsKey(array[i])){
                value = map.get(array[i])+1;
            }else{
                value=1;
            }
            map.put(array[i],value);
        }
        int length = array.length/2;
        for (Integer i:map.keySet()) {
            if(map.get(i)>length){
                return i;
            }
        }
        return 0;
    }
    public static void main(String args[]){
        int[] p = {1,2,3,2,2,2,5,4,2};
        int a = MoreThanHalfNum_Solution(p);
        System.out.println(a);
    }

}

